package lab2rsagroup10;

import java.math.BigInteger;
import java.util.Random;

public class Util {
	
	/**
	 * Returns a BigInteger whose value is <code>x<sup>c</sup> mod n</code>.
	 * This method uses the square-and-multiply algorithm.
	 * @param x - The value to take modular exponentiation of.
	 * @param c - The exponent.
	 * @param n - The modulo.
	 */
	public static BigInteger modPow(final BigInteger x, 
			final BigInteger c, final BigInteger n) {
		BigInteger z  = BigInteger.ONE;
		
		for (int i = c.bitLength()-1; i >= 0; --i) {
			z = z.multiply(z).mod(n);
			if (c.testBit(i)) {
				z = z.multiply(x).mod(n);
			}
		}
		
		return z;
	}

	/**
	 * It returns randomly generated prime number n.
	 * by using miller-rabin algorithm
	 * @param bitlength
	 * @return prime number n
	 */
	public static BigInteger generatePrime(int bitlength){
		BigInteger p;
		do
			p = new BigInteger(bitlength, new Random());
		while(!(p.testBit(0) && millerRabin(p)));
		return p;
	}
	
	private static final BigInteger TWO = new BigInteger("2");
	/**
	 * @param n - prime number
	 * @return whether n is prime or not
	 */
	private static boolean millerRabin(BigInteger n){
		BigInteger m = n.subtract(BigInteger.ONE);
		int k = 0;
		while(m.mod(TWO).compareTo(BigInteger.ZERO)==0){
			m = m.divide(TWO);
			k++;
		}

		BigInteger a;
		do
			a = new BigInteger(n.bitLength(), new Random());
		while(a.compareTo(m) == 1 && a.compareTo(BigInteger.ZERO) != 0);
		BigInteger b;
		b = modPow(a, m, n);
		if(b.mod(n).compareTo(BigInteger.ONE)==0)
			return true;
		for(int i = 0; i <= k-1; i++){
			if(b.mod(n).compareTo(n.subtract(BigInteger.ONE))==0)
				return true;
			else
				b = modPow(b, TWO, n);
		}
		return false;
	}
		
	/**
	 * Returns the multiplicative inverse of x modulo m.
	 * <code>x<sup>-1</sup> mod m</code>. If x is not invertible
	 * modulo m, 0 is returned.
	 * @param x - The value to invert.
	 * @param m - The modulus.
	 * @return The inverse of x modulo m if x is invertible
	 * modulo m, else 0.
	 */
	public static BigInteger inv(final BigInteger x, final BigInteger m) {
		if (x.equals(BigInteger.ZERO)) {
			return BigInteger.ZERO;
		}
	    BigInteger m0 = m;
	    BigInteger x0 = x;
	    BigInteger t0 = BigInteger.ZERO;
	    BigInteger t = BigInteger.ONE;
	    BigInteger q = m0.divide(x0);
	    BigInteger r = m0.subtract(q.multiply(x0));
	    BigInteger temp;

	    while(r.compareTo(BigInteger.ZERO) == 1) {
	    	temp = t0.subtract(q.multiply(t)).mod(m);
	    	t0 = t;
	    	t = temp;
	    	m0 = x0;
	    	x0 = r;
	    	q = m0.divide(x0);
	    	r = m0.subtract(q.multiply(x0));
	    }
	    
	    if (x0.equals(BigInteger.ONE))
	    	return t;
	    
	    return BigInteger.ZERO;
	}
	
}
